package bTree.LeetCode;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class 太平洋大西洋水流问题 {
    List<List<Integer>> res = new ArrayList<>();
    int[][] d = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int row = heights.length;
        int line = heights[0].length;
        int[][] cnt = new int[row][line];
        //从大西洋出发
        boolean[][] visited = new boolean[row][line];
        for (int i = 0; i < line; i++) {
            if (!visited[0][i]) {
                dfs(visited, cnt, heights, 0, i);
            }
        }
        for (int i = 1; i < row; i++) {
            if (!visited[i][0]) {
                dfs(visited, cnt, heights, i, 0);
            }
        }
        //从太平洋出发
        boolean[][] visited2 = new boolean[row][line];
        for (int i = 0; i < line; i++) {
            if (!visited2[row-1][i]) {
                dfs(visited2, cnt, heights, row-1, i);
            }
        }
        for (int i = 0; i < row - 1; i++) {
            if (!visited2[i][line-1]) {
                dfs(visited2, cnt, heights, i, line-1);
            }
        }
        for (int i = 0; i < row; i++) {
            for (int i1 = 0; i1 < line; i1++) {
                if (cnt[i][i1] == 2) {
                    List<Integer> path = new ArrayList<>();
                    path.add(i);
                    path.add(i1);
                    res.add(path);
                }
            }
        }
        return res;
    }

    private void dfs(boolean[][] visited, int[][] cnt, int[][] heights, int row, int line) {
        if (visited[row][line]){
            return;
        }
        visited[row][line]=true;
        cnt[row][line]++;
        for (int i = 0; i < 4; i++) {
            int newRow=row+d[i][0];
            int newLine=line+d[i][1];
            if (newRow<0||newRow>=visited.length||newLine<0||newLine>=visited[0].length){
                continue;
            }
            if (heights[row][line]>heights[newRow][newLine]){
                continue;
            }
            dfs(visited, cnt, heights, newRow, newLine);

        }
    }
}